from os import device_encoding
from queue import Queue

class AMGraph:
    maxSize=100
    def __init__(self):
        self.vexs=[]    #顶点表
        self.arcs=[]    #邻接矩阵
        self.vexNum=None
        self.arcNum=None


class UndirectedGraph:
    # 整个图的初始化
    def __init__(self,graphNumber):     #graphNumber 为初始化顶点个数
        self.graph=AMGraph()
        self.Visited=[]
        self.q=Queue(10)  #队列初始化
        # Visited 列表初始化
        for i in range(graphNumber):
            self.Visited.append(0)
        fileCount=0   # 记录文件的总行数
        self.graph.vexNum=graphNumber
        with open("./ax1.txt",'r',encoding='utf-8') as f:
            while True:
                text=f.readline()
                if not text:
                    break
                else:
                    fileCount+=1
            f.seek(0,0)
            self.graph.arcNum=fileCount-graphNumber
            for i in range(graphNumber):
                self.graph.vexs.append(f.readline().replace('\n',''))
            for i in range(AMGraph.maxSize):
                tempList=[]
                for j in range(AMGraph.maxSize):
                    tempList.append(0)
                self.graph.arcs.append(tempList)
            for i in range(fileCount-graphNumber):
                tempchars=f.readline()
                tempx=self.graph.vexs.index(tempchars[0])
                tempy=self.graph.vexs.index(tempchars[2])
                self.graph.arcs[tempx][tempy]=1
                self.graph.arcs[tempy][tempx]=1

    def deepSearch(self,index):
        # 深度优先遍历，递归实现
        self.Visited[index]=1
        print(self.graph.vexs[index],end='\t')
        for i in range(self.graph.vexNum):
            if self.graph.arcs[index][i]!=0 and self.Visited[i]!=1:
                self.deepSearch(i)

    def deepSearchByStack(self,begin):
        # 堆栈实现深度优先算法

        print("\n堆栈实现深度优先遍历")
        self.Visited=[0]*5
        charStack=[]
        intStack=[]
        charStack.append(self.graph.vexs[begin])
        i=0
        while(len(charStack)<5):
            for i in range(5):
                if self.graph.arcs[begin][i]!=0 and self.Visited[i]!=1 and (self.graph.vexs[i] not in charStack):
                    charStack.append(self.graph.vexs[i])
                    intStack.append(begin)
                    begin=i
                    break
            if i==4:
                begin=intStack.pop()
        for x in charStack:
            print(x,end='\t')
    
    def spanSearch(self,begin):
        # 队列实现广度优先遍历
        print('\n队列实现广度优先遍历')
        Visited=[0]*5
        self.q.put(begin)
        Visited[begin]=1
        while(not self.q.empty()):
            begin=self.q.get()
            print(self.graph.vexs[begin],end='\t')
            for i in range(self.graph.vexNum):
                if ((self.graph.arcs[begin][i] !=0) and (Visited[i]!=1)):
                    Visited[i]=1
                    self.q.put(i)

            
if __name__=='__main__':
    MainGraph=UndirectedGraph(5)
    print(MainGraph.graph.vexs)
    # print(MainGraph.graph.arcs)
    for i in range(5):
        for j in range(5):
            print(MainGraph.graph.arcs[i][j],end='\t')
        print()
    MainGraph.deepSearch(1)
    MainGraph.deepSearchByStack(1)
    MainGraph.spanSearch(1)